class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    /*
    总体思想：滑动窗口的思想
    右边界先移动，直到包含T中的所有字符，然后左边界再向左移动，使得子区间长度越来越小，
    最小覆盖子串就产生在左边界向右移动的过程中。
    Tfreq[]用来存T字符串的频数数组
    winfreq[] 滑动窗口的字符频数数组
    当右边界的元素在T中没有，right++
    如果右边界的元素在T中存在，并且滑动窗口中该元素出现的频次小于T字符串中该元素出现的频次
            distence++;(distence表示滑动窗口中包含了多少个T中的字符)
    wintreq[right]++;
    right++;
    
    当滑动窗口中包含了T的所有元素，也就是distence==Tlen，左边界开始向右移动
    当左边界的元素没有在T中，就让left++;
    当左边界元素在滑动窗口的频数数组的值==T的频数数组所对应的值，left再++的话，distence必须--
    左边界元素在滑动窗口的频数数组的值--
    左边界向右移动
    */
    string minWindow(string s, string t) {
        // write code here
        int slen=s.size();
        int tlen=t.size();
        if(slen==0||tlen==0||slen<tlen)
            return "";
        unordered_map<char, int>tfreq;
        unordered_map<char, int>winfreq;
        //vector<int>tfreq(128,0);
        //vector<int>winfreq(128,0);
        for(auto &x:t)
            tfreq[x]++;
        int left=0,right=0,distence=0;
        int minlen=slen+1;
        int begin=0;
        while(right<slen)
        {
            if(tfreq[s[right]]==0) //当有边界的元素T中没有
            {
                right++;continue;
            }
            if(winfreq[s[right]]<tfreq[s[right]]) //当滑动窗口中右边界的元素的频次小于T中频次
            {
                distence++;
            }
            winfreq[s[right]]++;
            right++;
            while(distence==tlen)
            {
                if(right-left<minlen)
                { 
                    minlen=right-left;
                    begin=left;
                }
                if(tfreq[s[left]]==0)
                {
                    left++;
                    continue;
                }
                if(winfreq[s[left]]== tfreq[s[left]])
                {
                    distence--;
                }
                winfreq[s[left]]--;
                left++;
            }
        }
        if(minlen==slen+1)
            return "";
        return s.substr(begin,minlen);
    }
};